//
// Created by daiyizheng on 2022/4/12.
//

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    //动态规划，完全背包
    //状态表示： dp[i][j] 表示从前i种硬币中选，且总金额恰好为j的所有选法集合的方案数。
    //状态计算： dp[i][j] = dp[i-1][j]+dp[i-1][j-coins[i]]+dp[i-1][j-2*coins[i]],,,,,,+dp[i-1][j-k*coins[i]]
    int change(int amount, vector<int>& coins) {
        //定义维度
        int n =coins.size();
        vector<vector<int>>dp(n + 1, vector<int>(amount + 1 , 0));
        //初始化
        dp[0][0] = 1;
        for (int i = 1; i <=n ; ++i) {
            int v = coins[i-1];
            for (int j = 0; j <=amount ; ++j) {
                for (int k = 0; k*v <= j; ++k) {
                    dp[i][j] = dp[i][j] + dp[i-1][j-k*v];////状态计算方程
                }
            }

        }
        return dp[n][amount];
    }
    //空间压缩
    int change1(int amount, vector<int>& coins) {
        // dp[c]：硬币列表能够凑成总金额为 c 的组合数。
        vector<int> dp(amount + 1);

        // 凑成总金额为 0 的组合就是不选择任何硬币
        dp[0] = 1;

        for (int coin : coins) {
            for (int c = coin; c <= amount; c++) {
                dp[c] = dp[c] + dp[c - coin];
            }
        }

        return dp[amount];
    }
};